/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-insert-position
   @Language: C++
   @Datetime: 16-02-09 05:17
   */

// Method 1
class Solution {
	/** 
	 * param A : an integer sorted array
	 * param target :  an integer to be inserted
	 * return : an integer
	 */
public:
	int searchInsert(vector<int> &A, int target) {
		// write your code here
		int begin=0, end=A.size(), mid;
		while(begin<end){
			mid = (begin-end)/2+begin;
			if (A[mid]>=target) end=mid;
			else begin=mid+1;
		}
		return begin;
	}
};

// Method 2, using stl algorithm
class Solution {
	/** 
	 * param A : an integer sorted array
	 * param target :  an integer to be inserted
	 * return : an integer
	 */
public:
	int searchInsert(vector<int> &A, int target) {
		// write your code here
		return lower_bound(A.begin(),A.end(),target)-A.begin();
	}
};